package com.lw.leetcode.tree.c;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 745. 前缀和后缀搜索
 *
 * @author liw
 * @version 1.0
 * @date 2022/7/14 10:03
 */
public class WordFilter {


    public static void main(String[] args) {

        // 0
        String[] arr = {"apple"};
        WordFilter test = new WordFilter(arr);
        System.out.println(test.f("apple", "pple"));

        // 0
//        String[] arr = {"abbba", "abba"};
//        WordFilter test = new WordFilter(arr);
//        System.out.println(test.f("ab", "ba"));


    }

    private Node root = new Node(-1);
    private Node item = new Node(-1);

    public WordFilter(String[] words) {
        int length = words.length;
        for (int i = length - 1; i >= 0; i--) {
            String word = words[i];
            add(root, word.toCharArray(), 0, i, 3);
        }
    }

    public int f(String pref, String suff) {
        return find(root, pref, suff, 0);
    }

    private int find(Node node, String pref, String suff, int index) {
        if (node == null) {
            return -1;
        }
        int a = pref.length();
        int b = suff.length();
        int index2 = b - index - 1;
        if (a == b && a - 1 == index) {
            long v = (1L << (32 + pref.charAt(index) - 'a')) + (1 << (suff.charAt(index2) - 'a'));
            return node.map.getOrDefault(v, item).var;
        }
        if (index >= b) {
            long v = (1L << (32 + pref.charAt(index) - 'a')) + (1 << 26);
            if (a - 1 == index) {
                return node.map.getOrDefault(v, item).var;
            } else {
                Node no = node.map.get(v);
                return find(no, pref, suff, index + 1);
            }
        }

        if (index >= a) {
            long v = (1L << 58) + (1 << (suff.charAt(index2) - 'a'));
            if (b - 1 == index) {

                return node.map.getOrDefault(v, item).var;
            } else {
                Node no = node.map.get(v);
                return find(no, pref, suff, index + 1);
            }
        }
        long v = (1L << (32 + pref.charAt(index) - 'a')) + (1 << (suff.charAt(index2) - 'a'));
        Node no = node.map.get(v);
        return find(no, pref, suff, index + 1);
    }

    private void add(Node node, char[] arr, int index, int i, int flag) {
        int length = arr.length;
        if (length == index) {
            return;
        }
        int st = arr[index] - 'a';
        int end = arr[length - 1 - index] - 'a';
        long v = 0;
        Map<Long, Node> map = node.map;
        if (flag == 1) {
            v = (1L << 58) + (1 << end);
            if (!map.containsKey(v)) {
                map.put(v, new Node(i));
            }
            add(map.get(v), arr, index + 1, i, flag);
            return;
        }


        if (flag == 2) {
            v = (1L << (st + 32)) + (1 << 26);
            if (!map.containsKey(v)) {
                map.put(v, new Node(i));
            }
            add(map.get(v), arr, index + 1, i, flag);
            return;
        }

        v = (1L << (st + 32)) + (1 << 26);
        if (!map.containsKey(v)) {
            Node no = new Node(i);
            map.put(v, no);
        }
        add(map.get(v), arr, index + 1, i, 2);
        v = (1L << 58) + (1 << end);
        if (!map.containsKey(v)) {
            Node no = new Node(i);
            map.put(v, no);
        }
        add(map.get(v), arr, index + 1, i, 1);
        v = (1L << (st + 32)) + (1 << end);
        if (!map.containsKey(v)) {
            Node no = new Node(i);
            map.put(v, no);
        }
        add(map.get(v), arr, index + 1, i, flag);
    }

    private static class Node {
        private int var;

        public Node(int var) {
            this.var = var;
        }

        private Map<Long, Node> map = new HashMap<>();
    }

}
